package 力扣._437_路径综合3;

import 力扣.公用数据结构.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    // dfs套dfs

    public long dfs(TreeNode root, long targetSum) {
        if (root == null)
            return 0;
        long sum = 0;
        if (root.val == targetSum) {
            sum++;
            System.out.println(root + ", " + targetSum);
        }
        // 当前节点开始，左右子树开始
        // 不能断开，要连续
        sum += dfs(root.left, targetSum - root.val);
        sum += dfs(root.right, targetSum - root.val);

        return sum;
    }

    int total = 0;

    void dfs1(TreeNode root, int targetSum) {
        if (root == null)
            return;
        total += dfs(root, targetSum);
        dfs1(root.left, targetSum);
        dfs1(root.right, targetSum);
    }

    public int pathSum(TreeNode root, int targetSum) {
        dfs1(root, targetSum);
        return total;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.stringToTreeNode("[1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]");
        int target = 0;
        int i = new Solution().pathSum(treeNode, target);
        System.out.println(i);
    }
}